package sortalg

import "fmt"

/**
快速排序
*/

type QuickSort struct {
	keyList []int
}

func NewQuickSort(sourceList []int) *QuickSort {
	qs := &QuickSort{
		keyList: sourceList,
	}

	qs.insertSort()

	return qs
}

func (qs *QuickSort) insertSort() {
	qs.doSort(0, len(qs.keyList)-1)
}

func (qs *QuickSort) doSort(low int, high int) {
	if low < high {
		partion := qs.partion(low, high)
		qs.doSort(low, partion-1)
		qs.doSort(partion+1, high)
	}
}

func (qs *QuickSort) partion(low int, high int) int {
	keyValue := qs.keyList[low]
	for ; low < high; {
		for ; qs.keyList[high] > keyValue && high > low; {
			high--
		}
		qs.keyList[low] = qs.keyList[high]

		for ; qs.keyList[low] < keyValue && high > low; {
			low++
		}
		qs.keyList[high] = qs.keyList[low]
	}

	qs.keyList[low] = keyValue
	return low
}

func (qs *QuickSort) Print() {
	fmt.Println(qs.keyList)
}
